package top.hkyzf.study.leetcode;

import org.junit.Test;

import java.util.*;

/**
 * @author 朱峰
 * @date 2022-1-29 16:05
 */
public class 八皇后_面试题0812 {
    public List<List<String>> solveNQueens(int n) {
        String[][] board = new String[n][n];
        for (String[] strs : board) {
            for (int i = 0; i < n; i++) {
                strs[i] = ".";
            }
        }
        List<List<String>> result = new LinkedList<>();
        dfs(board, 0, result);
        return result;
    }

    void dfs(String[][] board, int row, List<List<String>> result) {
        if (row > board.length-1) {
            List<String> list = new ArrayList<>();
            for (String[] strs : board) {
                list.add(Arrays.stream(strs).reduce("", (s1, s2) -> s1+s2));
            }
            result.add(list);
            return;
        }
        for (int col = 0; col < board.length; col++) {
            if (!check(board, row, col)) {
                continue;
            }
            board[row][col] = "Q";
            dfs(board, row + 1, result);
            board[row][col] = ".";
        }
    }

    /**
     * 检查是否可以放皇后
     * @param row 行
     * @param col 列
     * @return 返回 true 可放置， false 不可放置
     */
    boolean check(String[][] board, int row, int col) {
        // 检查列是否冲突
        for (String[] ints : board) {
            if ("Q".equals(ints[col])) {
                return false;
            }
        }
        // 检查左上方
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if ("Q".equals(board[i][j])) {
                return false;
            }
        }
        // 金叉右上方
        for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
            if ("Q".equals(board[i][j])) {
                return false;
            }
        }
        return true;
    }

    @Test
    public void testSolveNQueens () {
        int queenNum = 8;
		List<List<String>> result = solveNQueens(queenNum);
		for (List<String> strs : result) {
			System.out.println(strs);
		}
		System.out.println(result.size());
    }
}
